package com.example.summary.sort;

import com.alibaba.fastjson.JSONObject;
import org.springframework.util.CollectionUtils;

import java.util.*;

/**
 * Created by wzn on 2019/1/10.
 */
public class BianLiAoChaShu {

    private static Node initTree() {
        Node g = new Node(2, null, null);
        Node h = new Node(4, null, null);
        Node i = new Node(8, null, null);

        Node d = new Node(1, null, g);
        Node e = new Node(5, h, null);
        Node f = new Node(7, null, i);

        Node b = new Node(3, d, e);
        Node c = new Node(9, f, null);

        Node a = new Node(6, b, c);

        return a;
    }

    private static void printNode(Node node) {
        System.out.print(node.getData() + " ");
    }

    private static void qian(Node root) {
        if (null == root) {
            return;
        }
        printNode(root);
        qian(root.getLeftNode());
        qian(root.getRightNode());
    }

    private static void zhong(Node root) {
        if (null == root) {
            return;
        }
        zhong(root.getLeftNode());
        printNode(root);
        zhong(root.getRightNode());
    }

    private static void hou(Node root) {
        if (null == root) {
            return;
        }
        hou(root.getLeftNode());
        hou(root.getRightNode());
        printNode(root);
    }

    public void theFirstTraversal_Stack(Node root) {  //先序遍历
        Stack<Node> stack = new Stack<Node>();
        Node node = root;
        while (node != null || stack.size() > 0) {  //将所有左孩子压栈
            if (node != null) {   //压栈之前先访问
                printNode(node);
                stack.push(node);
                node = node.getLeftNode();
            } else {
                node = stack.pop();
                node = node.getRightNode();
            }
        }
    }

    public void theInOrderTraversal_Stack(Node root) {  //中序遍历
        Stack<Node> stack = new Stack<Node>();
        Node node = root;
        while (node != null || stack.size() > 0) {
            if (node != null) {
                stack.push(node);   //直接压栈
                node = node.getLeftNode();
            } else {
                node = stack.pop(); //出栈并访问
                printNode(node);
                node = node.getRightNode();
            }
        }
    }

    public void thePostOrderTraversal_Stack(Node root) {   //后序遍历
        Stack<Node> stack = new Stack<Node>();
        Stack<Node> output = new Stack<Node>();//构造一个中间栈来存储逆后序遍历的结果
        Node node = root;
        while (node != null || stack.size() > 0) {
            if (node != null) {
                output.push(node);
                stack.push(node);
                node = node.getRightNode();
            } else {
                node = stack.pop();
                node = node.getLeftNode();
            }
        }
        System.out.println(output.size());
        while (output.size() > 0) {

            printNode(output.pop());
        }
    }

    public static int sum(Node root) {
        int sum = 0;
        if (null == root) {
            return sum;
        }
        sum += root.getData();
        sum += sum(root.getLeftNode());
        sum += sum(root.getRightNode());
        return sum;
    }

    public static List<List<Integer>> cenci(Node root) {
        List<List<Integer>> lists = new ArrayList<>();
        Queue<Node> rootQueue = new LinkedList<>();
        rootQueue.offer(root);
        cenci(lists, rootQueue);
        return lists;
    }

    private static void cenci(List<List<Integer>> lists, Queue<Node> queues) {
        List<Integer> cenciList = new ArrayList<>();
        Queue<Node> cenciQueue = new LinkedList();

        while (!queues.isEmpty()) {
            Node poll = queues.poll();
            if (null != poll) {
                cenciList.add(poll.getData());
                if (null != poll.getLeftNode()) {
                    cenciQueue.add(poll.getLeftNode());
                }
                if (null != poll.getRightNode()) {
                    cenciQueue.add(poll.getRightNode());
                }
            }
        }

        if (!CollectionUtils.isEmpty(cenciList)) {
            lists.add(cenciList);
            cenci(lists, cenciQueue);
        }
    }

    public static List<List<Integer>> cenci2(Node root) {
        List<List<Integer>> lists = new ArrayList<>();
        cenci2(lists, 0, root);
        return lists;
    }

    private static void cenci2(List<List<Integer>> lists, int cen, Node node) {
        if (null == node) {
            return;
        }

        if (cen >= lists.size()) {
            lists.add(new ArrayList<>());
        }

        lists.get(cen++).add(node.getData());
        cenci2(lists, cen, node.getLeftNode());
        cenci2(lists, cen, node.getRightNode());
    }

    public static void main(String[] args) {
//        System.out.println("qian");
//        qian(initTree());
//        System.out.println("");
//
//        System.out.println("zhong");
//        zhong(initTree());
//        System.out.println("");
//
//        System.out.println("hou");
//        hou(initTree());
//        System.out.println("");
//
//        System.out.println("sum");
//        System.out.println(sum(initTree()));

        System.out.println("cenci");
        System.out.println(JSONObject.toJSONString(cenci(initTree())));



    }

}
